package com.axzh.interview.base;

import java.util.Arrays;

public class MinimumSpanningTree {

	public static void main(String[] args) {
		int[] V = { 1, 2, 3, 4, 5, 6 };
		Edge[] E = new Edge[10];
		E[0] = new Edge(1, 2, 6);
		E[1] = new Edge(1, 3, 1);
		E[2] = new Edge(1, 4, 5);
		E[3] = new Edge(2, 3, 5);
		E[4] = new Edge(2, 5, 3);
		E[5] = new Edge(3, 4, 5);
		E[6] = new Edge(3, 5, 6);
		E[7] = new Edge(3, 6, 4);
		E[8] = new Edge(4, 6, 2);
		E[9] = new Edge(5, 6, 6);
		MinimumSpanningTree.kruskal(V, E);
		
		int max = Integer.MAX_VALUE;
		int[][] graph = { { max, 4, max, max, max, max, max, 8, max },
				{ 4, max, 8, max, max, max, max, 11, max },
				{ max, 8, max, 7, max, 4, max, max, 2 },
				{ max, max, 7, max, 9, 14, max, max, max },
				{ max, max, max, 9, max, 10, max, max, max },
				{ max, max, 4, 14, 10, max, 2, max, max },
				{ max, max, max, max, max, 2, max, 1, 6 },
				{ 8, 11, max, max, max, max, 1, max, 7 },
				{ max, max, 2, max, max, max, 6, 7, max } };
		int[][] map = new int[][] {
				{ 0, 10, max, max, max, 11, max, max, max },
				{ 10, 0, 18, max, max, max, 16, max, 12 },
				{ max, max, 0, 22, max, max, max, max, 8 },
				{ max, max, 22, 0, 20, max, max, 16, 21 },
				{ max, max, max, 20, 0, 26, max, 7, max },
				{ 11, max, max, max, 26, 0, 17, max, max },
				{ max, 16, max, max, max, 17, 0, 19, max },
				{ max, max, max, 16, 7, max, 19, 0, max },
				{ max, 12, 8, 21, max, max, max, max, 0 } };
		String[] vertics = { "a", "b", "c", "d", "e", "f", "g", "h", "i" };
		
		MinimumSpanningTree.prim(graph, vertics, 0);
		
		MinimumSpanningTree.prim(map, vertics, 0);
		
		MinimumSpanningTree.prim(graph);
	}

	public static void kruskal(int[] vex, Edge[] edge) {
		int num = vex.length;
		int[] vertics = new int[num + 1];
		Edge[] result = new Edge[num];
		int k = 0;
		Arrays.sort(edge);
		for (int i = 0; i < edge.length; i++) {
			int start = edge[i].s;
			int end = edge[i].e;
			if (start == end) {
				continue;
			}
			int e1 = getEnd(vertics, start);
			int e2 = getEnd(vertics, end);
			if (e1 != e2) {
				vertics[e1] = e2;
				result[k++] = edge[i];
			}
		}
		int weight = 0;
		for (int i = 0; i < k; i++) {
			System.out.println(result[i].s + "->" + result[i].e + ": "
					+ result[i].w);
			weight += result[i].w;
		}
		System.out.println(weight);
	}

	public static void prim(int[][] graph, String[] vertics, int s) {
		int n = graph.length;
		int[] curWeight = new int[n];
		int[] close_vertex = new int[n];
		boolean[] visted = new boolean[n];
		for (int i = 0; i < n; i++) {
			curWeight[i] = graph[0][i];
			close_vertex[i] = 0;
			visted[i] = false;
		}
		// curWeight[s]=0;
		int sum = 0;
		visted[0] = true;
		for (int i = 0; i < n - 1; i++) {
			// if(i==s && s!=0){
			// continue;
			// }
			int min = Integer.MAX_VALUE;
			int k = 0;
			for (int j = 0; j < n; j++) {
				if (curWeight[j] > 0 && curWeight[j] < min && !visted[j]) {
					min = curWeight[j];
					k = j;
				}
			}
			System.out.println(vertics[close_vertex[k]] + "->" + vertics[k]
					+ ": " + min);
			sum += min;
			curWeight[k] = 0;
			visted[k] = true;
			for (int j = 0; j < n; j++) {
				if (graph[k][j] < curWeight[j] && !visted[j]) {
					curWeight[j] = graph[k][j];
					close_vertex[j] = k;
				}
			}
		}
		System.out.println(sum);
	}

	public static void prim(int[][] graph) {

		char[] c = new char[] { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I' };
		int n = c.length;
		int[] lowcost = new int[n];
		int[] mst = new int[n];
		int i, j, min, minid, sum = 0;

		for (i = 1; i < n; i++) {
			lowcost[i] = graph[0][i];
			mst[i] = 0;
		}

		for (i = 1; i < n; i++) {

			min = Integer.MAX_VALUE;
			minid = 0;
			for (j = 1; j < n; j++) {
				if (lowcost[j] < min && lowcost[j] != 0) {
					min = lowcost[j];
					minid = j;
				}
			}
			System.out.println(c[mst[minid]] + "到" + c[minid] + " 权值：" + min);

			sum += min;
			lowcost[minid] = 0;

			for (j = 1; j < n; j++) {
				if (graph[minid][j] < lowcost[j]) {
					lowcost[j] = graph[minid][j];
					mst[j] = minid;
				}
			}
		}

		System.out.println("sum:" + sum);

	}

	// 并查集
	private static int getEnd(int[] vertics, int start) {
		// int tmp=start-1;
		while (vertics[start] != 0) {
			start = vertics[start];
		}
		return start;
	}
	
	private static class Edge implements Comparable<Edge> {

		public int s, e, w;

		public Edge(int s, int e, int w) {
			this.s = s;
			this.e = e;
			this.w = w;
		}

		@Override
		public int compareTo(Edge o) {
			return this.w > o.w ? 1 : (this.w == o.w ? 0 : -1);
		}

	}

}


